package edu.gatech.coc.sirana.graph;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Stack;

import net.util.Debug;

import edu.gatech.coc.sirana.detection.LevenshteinDistance;
import edu.gatech.coc.sirana.exception.SIRANAException;
import edu.gatech.coc.sirana.parser.ClientLogItem;
import edu.gatech.coc.sirana.util.CONSTANT;

public class OnlineGraph {
	static private int nodeId =1;
	private HashMap<Integer, FDANode> nodes = new HashMap<Integer, FDANode> ();	
	private HashMap<String, FDAEdge> edges = new HashMap<String, FDAEdge> ();
	
	public HashMap<Integer, FDANode> getNodes() {
		return nodes;
	}

	public void setNodes(HashMap<Integer, FDANode> nodes) {
		this.nodes = nodes;
	}

	public HashMap<String, FDAEdge> getEdges() {
		return edges;
	}

	public void setEdges(HashMap<String, FDAEdge> edges) {
		this.edges = edges;
	}

	public OnlineGraph(){
		this.nodes	= new HashMap<Integer, FDANode>();
	}
	
	private void addNode(FDANode newNode, FDANode preNode){			
		newNode.setId(nodeId);				
		this.nodes.put(nodeId, newNode);				
		
		nodeId++;		
		
		if (preNode!=null){
			addEdge(preNode, newNode);
		}
	}
	
	private FDAEdge addEdge(FDANode src, FDANode snk){
		FDAEdge e = new FDAEdge(src, snk);
		snk.addInEdge(e);
		src.addOutEdge(e);
		
		String label = e.findLabel();
		if (!this.edges.containsKey(label)){
			this.edges.put(e.findLabel(), e);
		}
		
		return e;
	}
			
	private void pushBkNode(FDANode bkNode, Stack<FDANode> bkNodeStack){
		if (bkNodeStack.isEmpty()) bkNodeStack.add(bkNode);
		else {
			FDANode topBkNode = bkNodeStack.peek();
			if (bkNode.getId() < topBkNode.getId()){
				bkNodeStack.push(bkNode);
			}else if (bkNode.getId() > topBkNode.getId()){
				while(bkNode.getId() > bkNodeStack.pop().getId()){
					if (bkNodeStack.size()==0) break;
				}
				bkNodeStack.push(bkNode);
			}
		}
	}
	
	private void popBkNode(FDANode pointerNode, Stack<FDANode> bkNodeStack){
		while(!bkNodeStack.pop().isSame(pointerNode)){}			
	}
	
	private void printBkStack(Stack<FDANode> bkStack){
		Debug.println("---BkStack---");
		if (!bkStack.isEmpty())
			Debug.println("HEAD: " + bkStack.peek());
		for (FDANode fn : bkStack){
			Debug.println(fn.toString());
		}
		Debug.println("---BkStack Done---");
	}
	
	
	/**
	 * 
	 * @param sortedItemParsers
	 * @return Sorted interaction circles.
	 * 
	 * T8 is confusing case.
	 */
	public ArrayList<InteractionCycle> detectRecursiveInteractionCircles(ArrayList<ClientLogItem> sortedItemParsers){
		ArrayList<InteractionCycle> cycleList = new ArrayList<InteractionCycle> ();		

		ClientLogItem preItem = null;
		FDANode preNode = null;
		
		Stack<FDANode> bkNodeStack = new Stack<FDANode>();
		Util util = new Util();
		for (int itemIndex=0; itemIndex<sortedItemParsers.size(); itemIndex++){
			ClientLogItem pointerItem	= sortedItemParsers.get(itemIndex);
//			Debug.println( "===============Check item: " + pointerItem.getId() + "============");
	
			FDANode pointerNode = this.findNodeByAction(pointerItem.findAction());		

			if (itemIndex > 0){
				preItem = sortedItemParsers.get(itemIndex-1);
				preNode = this.findNodeByAction(preItem.findAction());
			}				
			
			if (pointerNode==null){/** a new node */
				FDANode newNode = new FDANode(pointerItem);
				this.addNode(newNode, preNode);
			}else{/** an existing nodes revisited */		
//				Debug.println("Pointer item: " + pointerItem);
//				Debug.println("An existing node: " + pointerNode.getId() + ", " + pointerNode.findLastVisit());
//				Debug.println("previous node: " + preNode.getId());
				FDAEdge newEdge = this.addEdge(preNode, pointerNode);
				
				if (newEdge.isBackEdge()){		
					if (pointerNode.findLastVisit().isLeaveEvent()){
						//leave event cannot be head item.
						pointerNode.addVisitingHistory(pointerItem);
						continue;
					}
					if (bkNodeStack.contains(pointerNode)){
						ClientLogItem pointerNodeLastVisit = pointerNode.findLastVisit();
						int pointerNodeLastPos = sortedItemParsers.indexOf(pointerNodeLastVisit);
						InteractionCycle ic = util.createICfromSublist(pointerNodeLastPos, itemIndex, sortedItemParsers);
						util.addInteractionCycle(cycleList, ic);
						
					}else{
//						Debug.println("---A backdge: node " + preNode.getId() + " to node " + pointerNode.getId());						
						ClientLogItem pointerNodeLastVisit = pointerNode.findLastVisit();
//						Debug.println("Pointer node last visit: " + pointerNodeLastVisit.toString() );
						int tarLastVisitPos = sortedItemParsers.lastIndexOf(pointerNodeLastVisit);
						
						InteractionCycle ic = util.createICfromSublist(tarLastVisitPos, itemIndex, sortedItemParsers);
						util.addInteractionCycle(cycleList, ic);
//						Debug.println("=====A new circle is added: \n" + ic.toString() + "\n====");
						
						this.pushBkNode(preNode, bkNodeStack);
					}
					pointerNode.addVisitingHistory(pointerItem);
				}else if (newEdge.isSelfCycle()){/** refreshing: pointer node == pre node */
//					Debug.println("--self cycle: " + pointerNode.getId());					
					for (;itemIndex < sortedItemParsers.size();itemIndex++){
						ClientLogItem cli = sortedItemParsers.get(itemIndex);
						if (cli.isSameAction(preItem)){ 
							preNode.addVisitingHistory(cli);
							
							ArrayList<ClientLogItem> selfCycle = new ArrayList<ClientLogItem>();
							selfCycle.add(cli);
							InteractionCycle ic = new InteractionCycle(selfCycle);
							util.addInteractionCycle(cycleList, ic);
//							Debug.println("A self cycle added:\n\t" + ic.toString());
						}else{
							itemIndex--;
							break;
						}
					}
					
					this.pushBkNode(preNode, bkNodeStack);
				}else{/** a forward edge that is in a circle */
//					Debug.println("A forward edge to existing node: " + pointerNode.getId());
					if (bkNodeStack.contains(pointerNode)){/** reach backedgeNode */
//						Debug.println("bkNode reached: " + bkNodeStack.peek());
						/** 
						 * if no more nodes or the next nodes is out of the circle, add a new circle.
						 */
						boolean isEndItem = (itemIndex==sortedItemParsers.size()-1);
						boolean isEndCircle = false;
						if (!isEndItem){
							ClientLogItem nextItem = sortedItemParsers.get(itemIndex+1);
							FDANode nextNode = findNodeByAction(nextItem.findAction());
							if (nextNode==null ||nextNode.getId() >= pointerNode.getId()){//new node or next node is out of the cycle
								isEndCircle = true;
							}									
						}
						
						if (isEndCircle){	
							//pop the bkNode and find it last visit
							this.popBkNode(pointerNode, bkNodeStack);
							
							ClientLogItem bkEdgeLastVisit = pointerNode.findLastVisit();							
							int bkEdgeLastPos = sortedItemParsers.indexOf(bkEdgeLastVisit);														
							int circleStartNodeLastPos = bkEdgeLastPos+1;
//							Debug.println("Reach to end of circle: Node " + pointerNode.getId() + ", item: " + pointerItem + " Last visit pos: "+ bkEdgeLastPos);
							
							InteractionCycle ic = util.createICfromSublist(circleStartNodeLastPos, itemIndex+1, sortedItemParsers);
							
							util.addInteractionCycle(cycleList, ic);	
//							Debug.println("=====A last repetitionis added: \n" + ic.toString() + "====");												
						}	
					}//end of same as backege node
					pointerNode.addVisitingHistory(pointerItem);
				}//end of an existing nodes revisited
			}//end of handling a ClientLogItem
		}//end of for 
		
		Collections.sort(cycleList);
		return cycleList;
	}
	
//	static public void addInteractionCycle(Collection<InteractionCycle> cycleList, InteractionCycle ic){
//		if (ic.isInteractiveCycle()) cycleList.add(ic);
//	}
	
	public ArrayList<InteractionCycle> removeRedundantCycles(ArrayList<InteractionCycle> redundantCycles){
//		Debug.println("REmove redundance from " + redundantCycles.size() + " cycles.");
		ArrayList<ArrayList<FDANode>> cleanNodeListCollection = new ArrayList<ArrayList<FDANode>>();
		ArrayList<InteractionCycle> nonRedundantCycles = new ArrayList<InteractionCycle>();
		
		for (int i=0; i<redundantCycles.size(); i++){
			InteractionCycle ic = redundantCycles.get(i);
			
			ArrayList<FDANode> fNodes = this.findNodeGroupByItems(ic.getItems());			
			if (!containNodeList(cleanNodeListCollection, fNodes) && ic.isInteractiveCycle()){
				cleanNodeListCollection.add(fNodes);
				
				nonRedundantCycles.add(ic);
//				Debug.println("\n***" + ic.toString() + " added as a nonRedun cycle.");
			}
		}
//		Debug.println("After remove redundance, there are " + nonRedundantCycles.size() + " cycles");
		return nonRedundantCycles;
	}
	
	private boolean containNodeList(ArrayList<ArrayList<FDANode>> nodeListCollection, ArrayList<FDANode> nodeList){
		for (ArrayList<FDANode> nl: nodeListCollection){
			if (isSameNodesInDifferentOrder(nl, nodeList)) return true;
		}
		
		return false;
	}
	/**
	 * Two nodes collections having the same nodes are the same.
	 * @param c1
	 * @param c2
	 * @return
	 */
	private boolean isSameNodesInDifferentOrder(ArrayList<FDANode> fn1, ArrayList<FDANode> fn2){
		
		if (fn1.size()!=fn2.size()) return false;
		
		for (FDANode n1: fn1){
			if (!fn2.contains(n1)) return false;
		}
		
		for (int i=0; i<fn1.size(); i++){
			FDANode n1 = fn1.get(i);
			if (!fn2.contains(n1)) return false;
			int iInFn2 = fn2.indexOf(n1);
			if (iInFn2 == i) return false;
		}		
		
		return true;
	}
	
	private FDANode findNodeByAction(String nodeAction) {
		for (int nId: this.nodes.keySet()){
			FDANode n = this.nodes.get(nId);
			if (n.getAction().equals(nodeAction)) return n;
		}
		
		return null;
	}
	
	ArrayList<FDANode> findNodeGroupByItems(ArrayList<ClientLogItem> clis){
//		Debug.println("findNodeGroupByItems: " + clis);
		ArrayList<FDANode> fNodes = new ArrayList<FDANode>();
		
		for (ClientLogItem c: clis){
			FDANode fn = this.findNodeByAction(c.findAction());
			if (fn==null){
				throw new SIRANAException("No node found for client log item: \n\t" + c);
			}else{
				fNodes.add(fn);
			}
		}
		
		return fNodes;
	}	
	
	int[] findNodeIdList(ArrayList<ClientLogItem> clis){
		int[] idList = new int[clis.size()];
		for (int i=0; i<clis.size(); i++){
			ClientLogItem c = clis.get(i);
			FDANode fn = this.findNodeByAction(c.findAction());
			if (fn==null){
				throw new SIRANAException("No node found for client log item: \n\t" + c);
			}else{
				idList[i] = fn.getId();
			}
		}
		return idList;
	}
	
	private double computeCycleSimilarity(InteractionCycle pointerCycle, InteractionCycle targetCycle){
		ArrayList<ClientLogItem> pointerItems = pointerCycle.getItems();
		ArrayList<ClientLogItem> targetItems = targetCycle.getItems();
		int[] pointerIdList = this.findNodeIdList(pointerItems);
		int[] targetIdList = this.findNodeIdList(targetItems);
		
		
		LevenshteinDistance ed = new LevenshteinDistance();
		int distance = ed.compute(pointerIdList, targetIdList);
		
		double similarity = (double)distance/pointerIdList.length;
		
		return similarity;
	}
	
	public boolean isSimilarCycles(InteractionCycle pointerCycle, InteractionCycle targetCycle){
		double similar = this.computeCycleSimilarity(pointerCycle, targetCycle);
		
		return similar > CONSTANT.SIMILAR_THRESHOLD;
	}
}
